package com.lhcai.classify.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 200. 岛屿数量
 * BFS解法
 *
 * @author liuhuaicai
 * @create 2024-05-27 21:45
 */
public class LC_BFS200 {
    public static void main(String[] args) {
        LC_BFS200 lcBfs200 = new LC_BFS200();
        char[][] chars = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
        lcBfs200.numIslands(chars);
    }

    public int numIslands(char[][] grid) {
        int res = 0;
        Queue<int[]> ints = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    ints.add(new int[]{i, j});
                    bfs(grid, ints);
                    res += 1;
                }
            }
        }
        return res;
    }

    private void bfs(char[][] grid, Queue<int[]> queue) {
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            // 获取横纵坐标
            int x = poll[0];
            int y = poll[1];
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0') {
               continue;
            }
            grid[x][y] = '0';
            // 向上
            queue.add(new int[]{x - 1, y});
            // 向下
            queue.add(new int[]{x + 1, y});
            // 向左
            queue.add(new int[]{x, y - 1});
            // 向右
            queue.add(new int[]{x, y + 1});
        }
    }
}
